Ternary expression parser¶
Time: O(N); Space: O(1); medium
Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression.
You can always assume that the given expression is valid and only consists of: * digits 0-9 * ?, : * T and F (T and Frepresent True and False respectively).
Example 1:
Input: expression = “T?2:3”
Output: “2”
Explanation:
If True, then result is 2; otherwise result is 3.
Example 2:
Input: expression = “F?1:T?4:5”
Output: “4”
Explanation:
The conditional expressions group right-to-left.
Using parenthesis, it is read/evaluated as:
“(F ? 1 : (T ? 4 : 5))” “(F ? 1 : (T ? 4 : 5))”
-> “(F ? 1 : 4)” or -> “(T ? 4 : 5)”
-> “4” -> “4”
Example 3:
Input: expression = “T?T?F:5:3”
Output: “F”
Explanation:
The conditional expressions group right-to-left.
Using parenthesis, it is read/evaluated as:
“(T ? (T ? F : 5) : 3)” “(T ? (T ? F : 5) : 3)”
-> “(T ? F : 3)” or -> “(T ? F : 5)”
-> “F” -> “F”
Constraints:
The length of the given string is <= 10000.
Each number will contain only one digit.
The conditional expressions group right-to-left (as usual in most languages).
The condition will always be either T or F. That is, the condition will never be a digit.
The result of the expression will always evaluate to either a digit 0-9, T or F.
[1]:
class Solution1(object):
def parseTernary(self, expression) -> str:
"""
:type expression: str
:rtype: str
"""
if not expression:
return ""
stack = []
for c in expression[::-1]:
if stack and stack[-1] == '?':
stack.pop() # pop '?'
first = stack.pop()
stack.pop() # pop ':'
second = stack.pop()
if c == 'T':
stack.append(first)
else:
stack.append(second)
else:
stack.append(c)
return str(stack[-1])
[2]:
s = Solution1()
expression = "T?2:3"
assert s.parseTernary(expression) == "2"
expression = "F?1:T?4:5"
assert s.parseTernary(expression) == "4"
expression = "T?T?F:5:3"
assert s.parseTernary(expression) == "F"